package com.lint.code.sort;

public class SortDemo {

    private static   int [] arr = {4,3,7,2,5,1,8,6
     };


    public static void main(String[] args) {

//        bubbleSort(arr);
//        insertSort(arr);
        qSort(arr,0,7);
//        int[] selection = selection(arr);
        for (int i=0;i < arr.length;i++){
            System.out.println(arr[i]);
        }
    }
    public static void qSort(int[] arr, int head, int tail) {
        if (head >= tail || arr == null || arr.length <= 1) {
            return;
        }
        int i = head, j = tail, pivot = arr[(head + tail) / 2];

        while (i <= j) {
            while (arr[i] < pivot) {
                ++i;
            }
            while (arr[j] > pivot) {
                --j;
            }
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                ++i;
                --j;
            } else if (i == j) {
                ++i;
            }
        }
        qSort(arr, head, j);
        qSort(arr, i, tail);
    }

    public static void insertSort(int [] arr){
        int preIndex;
        int current;
        for (int i = 1; i < arr.length ; i++) {
            preIndex = i -1;
            current = arr[i];
            while (preIndex >=0 && arr[preIndex] > arr[preIndex+1]  ){
                arr[preIndex+1] = arr[preIndex];
                arr[preIndex] = current;
                preIndex --;
            }
        }
    }

    public static int [] selection(int [] arr){

//        int [] a = new int[arr.length];

        for (int i= 0;i<arr.length;i++){
            int s = arr[i];
            int index = i;
            for (int j= i;j<arr.length;j++){
                if (s > arr[j]){
                    s = arr[j];
                    index = j;
                }
            }
            arr[index] =  arr[i] ;
            arr[i] = s;
        }
        return arr;
    }


    public static void bubbleSort(int [] arr){
        for (int i=0;i<arr.length;i++){
            for (int j=0;j<arr.length;j++){
                if (arr[j] > arr[i]){
                    int s = arr[i];
                    arr[i] = arr[j];
                    arr[j] = s;
                }
            }
        }
    }

}
